871. 最低加油次数

为保证权益，题目请参考 871. 最低加油次数(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution
{
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations)
    {
        int ans = 0;
        int pos = 0;
        int tank = startFuel;
        priority_queue<int> pri;
        for (int i = 0; i < stations.size(); ++i)
        {
            int d = stations[i][0] - pos;

            while (tank - d < 0)
            {
                if (!pri.empty())
                {
                    tank += pri.top();
                    pri.pop();
                    ans++;
                }
                else
                {
                    return -1;
                }
            }
            tank -= d;
            pos += d;
            pri.push(stations[i][1]);
        }

        while (pos + tank < target && !pri.empty())
        {
            tank += pri.top();
            pri.pop();
            ans++;
        }

        if (pos + tank >= target)
        {
            return ans;
        }
        else
        {
            return -1;
        }
    }
};

int main()
{
    vector<vector<int>> vec;

    vector<int> vec_1;
    vec_1.push_back(10);
    vec_1.push_back(60);
    vec.push_back(vec_1);

    vector<int> vec_2;
    vec_2.push_back(20);
    vec_2.push_back(30);
    vec.push_back(vec_2);

    vector<int> vec_3;
    vec_3.push_back(30);
    vec_3.push_back(30);
    vec.push_back(vec_3);

    vector<int> vec_4;
    vec_4.push_back(60);
    vec_4.push_back(40);
    vec.push_back(vec_4);

    Solution so;
    cout <<so.minRefuelStops(100, 10, vec) << endl;
    return 0;
}

Python

# 871. 最低加油次数
# https://leetcode.cn/problems/minimum-number-of-refueling-stops/


from typing import List
from queue import PriorityQueue


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        dp = [0] * (len(stations) + 1)
        dp[0] = startFuel

        for i in range(1, len(dp)):
            for j in range(i - 1, -1, -1):
                if dp[j] >= stations[i - 1][0]:
                    dp[j + 1] = max(dp[j + 1], dp[j] + stations[i - 1][1])

        ans = -1
        for i in range(len(dp)):
            if dp[i] >= target:
                ans = i
                break

        return ans


from queue import PriorityQueue


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        pri = PriorityQueue()

        cur_dist = startFuel

        count = 0

        for i in range(len(stations)):
            if cur_dist >= stations[i][0]:
                pri.put_nowait(-stations[i][1])
            else:

                while True:
                    if pri.qsize() == 0:
                        return -1

                    cur_dist = cur_dist + (-pri.get_nowait())
                    count += 1

                    if cur_dist >= stations[i][0]:
                        break

                pri.put_nowait(-stations[i][1])

        if cur_dist >= target:
            return count
        else:

            while True:
                if pri.qsize() == 0:
                    return -1

                cur_dist = cur_dist + (-pri.get_nowait())
                count += 1

                if cur_dist >= target:
                    break

            return count


if __name__ == "__main__":
    so = Solution()
    assert so.minRefuelStops(100, 25, [[25, 25], [50, 25], [75, 25]]) == 3